import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Code2509 {
    public static void main(String[] args) {
        Code2509 code2509 = new Code2509();
//        int i = code2509.longestSquareStreak(new int[]{10,2,13,16,8,9,13}); // -1
        int i = code2509.longestSquareStreak(new int[]{4,3,6,16,8,2}); // 3
//        int i = code2509.longestSquareStreak(new int[]{4,5,4}); // -1
//        int i = code2509.longestSquareStreak(new int[]{2,4}); // 2
        System.out.println("输出 " + i);
    }

    /**
     * 给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：
     * <p>
     * 子序列的长度至少为 2 ，并且
     * 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。
     * 返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。
     * <p>
     * 子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。
     * <p>
     * <p>
     * 示例 1 ：
     * <p>
     * 输入：nums = [4,3,6,16,8,2]
     * 输出：3
     * 解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。
     * - 4 = 2 * 2.
     * - 16 = 4 * 4.
     * 因此，[4,16,2] 是一个方波.
     * 可以证明长度为 4 的子序列都不是方波。
     * 示例 2 ：
     * <p>
     * 输入：nums = [2,3,5,6,7]
     * 输出：-1
     * 解释：nums 不存在方波，所以返回 -1 。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/longest-square-streak-in-an-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int longestSquareStreak(int[] nums) {
        Arrays.sort(nums);

        int n=nums.length,max=nums[n-1],len=-1;
        int[] dp=new int[max+1];
        for(int i=0;i<n;i++){
            dp[nums[i]]=1;
        }
        for(int i=0;i<n;i++){
            int x=(int)Math.sqrt(nums[i]);
            if(x*x!=nums[i])continue;
            dp[nums[i]]=dp[x]+1;
        }
        for(int i=0;i<=max;i++){
            if(dp[i]>=2)len=Math.max(len,dp[i]);
        }
        return len;
    }

}
